package Leetcode.网格图;

import java.util.Arrays;

class 排布二进制网格的最少交换次数 {
    public int minSwaps(int[][] grid) {
        // 获取网格的行数
        int n = grid.length;
        // 创建一个数组来存储每行最后一个1的位置
        int[] pos = new int[n];
        // 初始化数组，所有位置设为-1
        Arrays.fill(pos, -1);
        
        // 遍历网格，找到每行最后一个1的位置
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                // 如果当前位置是1，则记录该位置，并退出内层循环
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }   
        }
        
        // 初始化交换次数
        int ans = 0;
        // 遍历pos数组，确保每个位置的值都小于等于其索引
        for (int i = 0; i < n; ++i) {
            int k = -1;
            // 从当前位置开始向后查找，找到第一个满足条件的值
            for (int j = i; j < n; ++j) {
                if (pos[j] <= i) {
                    // 如果找到，累加交换次数，并记录找到的位置
                    ans += j - i;
                    k = j;
                    break;
                }
            }
            // 如果找到了满足条件的位置，则进行交换，使其符合要求
            if (k >= 0) {
                for (int j = k; j > i; --j) {
                    // 交换位置
                    int temp = pos[j];
                    pos[j] = pos[j - 1];
                    pos[j - 1] = temp;
                }
            } else {
                // 如果没有找到满足条件的位置，则无法通过交换达到要求，返回-1
                return -1;
            }
        }
        // 返回总的交换次数
        return ans;
    }
}
